<html>
  <head>
  <title>game.py</title>
  </head>
  <body>
  <h3>game.py (<a href="../game.py">original</a>)</h3>
  <hr>
  <pre>
<span style="color: green; font-style: italic"># game.py
# -------
# Licensing Information: Please do not distribute or publish solutions to this
# project. You are free to use and extend these projects for educational
# purposes. The Pacman AI projects were developed at UC Berkeley, primarily by
# John DeNero (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# For more info, see http://inst.eecs.berkeley.edu/~cs188/sp09/pacman.html

</span><span style="color: blue; font-weight: bold">from </span>util <span style="color: blue; font-weight: bold">import </span><span style="font-weight: bold">*
</span><span style="color: blue; font-weight: bold">from </span>util <span style="color: blue; font-weight: bold">import </span>raiseNotDefined
<span style="color: blue; font-weight: bold">import </span>time<span style="font-weight: bold">, </span>os
<span style="color: blue; font-weight: bold">import </span>traceback

<span style="color: blue; font-weight: bold">try</span><span style="font-weight: bold">:
  </span><span style="color: blue; font-weight: bold">import </span>boinc
  _BOINC_ENABLED <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">True
except</span><span style="font-weight: bold">:
  </span>_BOINC_ENABLED <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">False

</span><span style="color: green; font-style: italic">#######################
# Parts worth reading #
#######################

</span><span style="color: blue; font-weight: bold">class </span>Agent<span style="font-weight: bold">:
  </span><span style="color: darkred">"""
  An agent must define a getAction method, but may also define the
  following methods which will be called if they exist:

  def registerInitialState(self, state): # inspects the starting state
  """
  </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>index<span style="font-weight: bold">=</span><span style="color: red">0</span><span style="font-weight: bold">):
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>index <span style="font-weight: bold">= </span>index

  <span style="color: blue; font-weight: bold">def </span>getAction<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>state<span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    The Agent will receive a GameState (from either {pacman, capture, sonar}.py) and
    must return an action from Directions.{North, South, East, West, Stop}
    """
    </span>raiseNotDefined<span style="font-weight: bold">()

</span><span style="color: blue; font-weight: bold">class </span>Directions<span style="font-weight: bold">:
  </span>NORTH <span style="font-weight: bold">= </span><span style="color: red">'North'
  </span>SOUTH <span style="font-weight: bold">= </span><span style="color: red">'South'
  </span>EAST <span style="font-weight: bold">= </span><span style="color: red">'East'
  </span>WEST <span style="font-weight: bold">= </span><span style="color: red">'West'
  </span>STOP <span style="font-weight: bold">= </span><span style="color: red">'Stop'

  </span>LEFT <span style="font-weight: bold">=       {</span>NORTH<span style="font-weight: bold">: </span>WEST<span style="font-weight: bold">,
                 </span>SOUTH<span style="font-weight: bold">: </span>EAST<span style="font-weight: bold">,
                 </span>EAST<span style="font-weight: bold">:  </span>NORTH<span style="font-weight: bold">,
                 </span>WEST<span style="font-weight: bold">:  </span>SOUTH<span style="font-weight: bold">,
                 </span>STOP<span style="font-weight: bold">:  </span>STOP<span style="font-weight: bold">}

  </span>RIGHT <span style="font-weight: bold">=      </span>dict<span style="font-weight: bold">([(</span>y<span style="font-weight: bold">,</span>x<span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">for </span>x<span style="font-weight: bold">, </span>y <span style="color: blue; font-weight: bold">in </span>LEFT<span style="font-weight: bold">.</span>items<span style="font-weight: bold">()])

  </span>REVERSE <span style="font-weight: bold">= {</span>NORTH<span style="font-weight: bold">: </span>SOUTH<span style="font-weight: bold">,
             </span>SOUTH<span style="font-weight: bold">: </span>NORTH<span style="font-weight: bold">,
             </span>EAST<span style="font-weight: bold">: </span>WEST<span style="font-weight: bold">,
             </span>WEST<span style="font-weight: bold">: </span>EAST<span style="font-weight: bold">,
             </span>STOP<span style="font-weight: bold">: </span>STOP<span style="font-weight: bold">}

</span><span style="color: blue; font-weight: bold">class </span>Configuration<span style="font-weight: bold">:
  </span><span style="color: darkred">"""
  A Configuration holds the (x,y) coordinate of a character, along with its
  traveling direction.

  The convention for positions, like a graph, is that (0,0) is the lower left corner, x increases
  horizontally and y increases vertically.  Therefore, north is the direction of increasing y, or (0,1).
  """

  </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>pos<span style="font-weight: bold">, </span>direction<span style="font-weight: bold">):
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>pos <span style="font-weight: bold">= </span>pos
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>direction <span style="font-weight: bold">= </span>direction

  <span style="color: blue; font-weight: bold">def </span>getPosition<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>pos<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>getDirection<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>direction

  <span style="color: blue; font-weight: bold">def </span>isInteger<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span>x<span style="font-weight: bold">,</span>y <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>pos
    <span style="color: blue; font-weight: bold">return </span>x <span style="font-weight: bold">== </span>int<span style="font-weight: bold">(</span>x<span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">and </span>y <span style="font-weight: bold">== </span>int<span style="font-weight: bold">(</span>y<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>__eq__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>other<span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span>other <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return False
    return </span><span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>pos <span style="font-weight: bold">== </span>other<span style="font-weight: bold">.</span>pos <span style="color: blue; font-weight: bold">and </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>direction <span style="font-weight: bold">== </span>other<span style="font-weight: bold">.</span>direction<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>__hash__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span>x <span style="font-weight: bold">= </span>hash<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>pos<span style="font-weight: bold">)
    </span>y <span style="font-weight: bold">= </span>hash<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>direction<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">return </span>hash<span style="font-weight: bold">(</span>x <span style="font-weight: bold">+ </span><span style="color: red">13 </span><span style="font-weight: bold">* </span>y<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>__str__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">"(x,y)="</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>pos<span style="font-weight: bold">)+</span><span style="color: red">", "</span><span style="font-weight: bold">+</span>str<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>direction<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>generateSuccessor<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>vector<span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Generates a new configuration reached by translating the current
    configuration by the action vector.  This is a low-level call and does
    not attempt to respect the legality of the movement.

    Actions are movement vectors.
    """
    </span>x<span style="font-weight: bold">, </span>y<span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>pos
    dx<span style="font-weight: bold">, </span>dy <span style="font-weight: bold">= </span>vector
    direction <span style="font-weight: bold">= </span>Actions<span style="font-weight: bold">.</span>vectorToDirection<span style="font-weight: bold">(</span>vector<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">if </span>direction <span style="font-weight: bold">== </span>Directions<span style="font-weight: bold">.</span>STOP<span style="font-weight: bold">:
      </span>direction <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>direction <span style="color: green; font-style: italic"># There is no stop direction
    </span><span style="color: blue; font-weight: bold">return </span>Configuration<span style="font-weight: bold">((</span>x <span style="font-weight: bold">+ </span>dx<span style="font-weight: bold">, </span>y<span style="font-weight: bold">+</span>dy<span style="font-weight: bold">), </span>direction<span style="font-weight: bold">)

</span><span style="color: blue; font-weight: bold">class </span>AgentState<span style="font-weight: bold">:
  </span><span style="color: darkred">"""
  AgentStates hold the state of an agent (configuration, speed, scared, etc).
  """

  </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>startConfiguration<span style="font-weight: bold">, </span>isPacman <span style="font-weight: bold">):
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>start <span style="font-weight: bold">= </span>startConfiguration
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>configuration <span style="font-weight: bold">= </span>startConfiguration
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>isPacman <span style="font-weight: bold">= </span>isPacman
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>scaredTimer <span style="font-weight: bold">= </span><span style="color: red">0

  </span><span style="color: blue; font-weight: bold">def </span>__str__<span style="font-weight: bold">( </span><span style="color: blue">self </span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>isPacman<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">"Pacman: " </span><span style="font-weight: bold">+ </span>str<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>configuration <span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">"Ghost: " </span><span style="font-weight: bold">+ </span>str<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>configuration <span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>__eq__<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>other <span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span>other <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return False
    return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>configuration <span style="font-weight: bold">== </span>other<span style="font-weight: bold">.</span>configuration <span style="color: blue; font-weight: bold">and </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>scaredTimer <span style="font-weight: bold">== </span>other<span style="font-weight: bold">.</span>scaredTimer

  <span style="color: blue; font-weight: bold">def </span>__hash__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span>hash<span style="font-weight: bold">(</span>hash<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>configuration<span style="font-weight: bold">) + </span><span style="color: red">13 </span><span style="font-weight: bold">* </span>hash<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>scaredTimer<span style="font-weight: bold">))

  </span><span style="color: blue; font-weight: bold">def </span>copy<span style="font-weight: bold">( </span><span style="color: blue">self </span><span style="font-weight: bold">):
    </span>state <span style="font-weight: bold">= </span>AgentState<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>start<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>isPacman <span style="font-weight: bold">)
    </span>state<span style="font-weight: bold">.</span>configuration <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>configuration
    state<span style="font-weight: bold">.</span>scaredTimer <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>scaredTimer
    <span style="color: blue; font-weight: bold">return </span>state

  <span style="color: blue; font-weight: bold">def </span>getPosition<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>configuration <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">None
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>configuration<span style="font-weight: bold">.</span>getPosition<span style="font-weight: bold">()

  </span><span style="color: blue; font-weight: bold">def </span>getDirection<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>configuration<span style="font-weight: bold">.</span>getDirection<span style="font-weight: bold">()

</span><span style="color: blue; font-weight: bold">class </span>Grid<span style="font-weight: bold">:
  </span><span style="color: darkred">"""
  A 2-dimensional array of objects backed by a list of lists.  Data is accessed
  via grid[x][y] where (x,y) are positions on a Pacman map with x horizontal,
  y vertical and the origin (0,0) in the bottom left corner.

  The __str__ method constructs an output that is oriented like a pacman board.
  """
  </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>width<span style="font-weight: bold">, </span>height<span style="font-weight: bold">, </span>initialValue<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">False</span><span style="font-weight: bold">, </span>bitRepresentation<span style="font-weight: bold">=</span><span style="color: blue">None</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span>initialValue <span style="color: blue; font-weight: bold">not in </span><span style="font-weight: bold">[</span><span style="color: blue; font-weight: bold">False</span><span style="font-weight: bold">, </span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">]: </span><span style="color: blue; font-weight: bold">raise </span>Exception<span style="font-weight: bold">(</span><span style="color: red">'Grids can only contain booleans'</span><span style="font-weight: bold">)
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>CELLS_PER_INT <span style="font-weight: bold">= </span><span style="color: red">30

    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width <span style="font-weight: bold">= </span>width
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>height <span style="font-weight: bold">= </span>height
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>data <span style="font-weight: bold">= [[</span>initialValue <span style="color: blue; font-weight: bold">for </span>y <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>height<span style="font-weight: bold">)] </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>width<span style="font-weight: bold">)]
    </span><span style="color: blue; font-weight: bold">if </span>bitRepresentation<span style="font-weight: bold">:
      </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_unpackBits<span style="font-weight: bold">(</span>bitRepresentation<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>__getitem__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>i<span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data<span style="font-weight: bold">[</span>i<span style="font-weight: bold">]

  </span><span style="color: blue; font-weight: bold">def </span>__setitem__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>key<span style="font-weight: bold">, </span>item<span style="font-weight: bold">):
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data<span style="font-weight: bold">[</span>key<span style="font-weight: bold">] = </span>item

  <span style="color: blue; font-weight: bold">def </span>__str__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span>out <span style="font-weight: bold">= [[</span>str<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">])[</span><span style="color: red">0</span><span style="font-weight: bold">] </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width<span style="font-weight: bold">)] </span><span style="color: blue; font-weight: bold">for </span>y <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height<span style="font-weight: bold">)]
    </span>out<span style="font-weight: bold">.</span>reverse<span style="font-weight: bold">()
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'\n'</span><span style="font-weight: bold">.</span>join<span style="font-weight: bold">([</span><span style="color: red">''</span><span style="font-weight: bold">.</span>join<span style="font-weight: bold">(</span>x<span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span>out<span style="font-weight: bold">])

  </span><span style="color: blue; font-weight: bold">def </span>__eq__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>other<span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span>other <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return False
    return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data <span style="font-weight: bold">== </span>other<span style="font-weight: bold">.</span>data

  <span style="color: blue; font-weight: bold">def </span>__hash__<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: green; font-style: italic"># return hash(str(self))
    </span>base <span style="font-weight: bold">= </span><span style="color: red">1
    </span>h <span style="font-weight: bold">= </span><span style="color: red">0
    </span><span style="color: blue; font-weight: bold">for </span>l <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">for </span>i <span style="color: blue; font-weight: bold">in </span>l<span style="font-weight: bold">:
        </span><span style="color: blue; font-weight: bold">if </span>i<span style="font-weight: bold">:
          </span>h <span style="font-weight: bold">+= </span>base
        base <span style="font-weight: bold">*= </span><span style="color: red">2
    </span><span style="color: blue; font-weight: bold">return </span>hash<span style="font-weight: bold">(</span>h<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>copy<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span>g <span style="font-weight: bold">= </span>Grid<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height<span style="font-weight: bold">)
    </span>g<span style="font-weight: bold">.</span>data <span style="font-weight: bold">= [</span>x<span style="font-weight: bold">[:] </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data<span style="font-weight: bold">]
    </span><span style="color: blue; font-weight: bold">return </span>g

  <span style="color: blue; font-weight: bold">def </span>deepCopy<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>copy<span style="font-weight: bold">()

  </span><span style="color: blue; font-weight: bold">def </span>shallowCopy<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span>g <span style="font-weight: bold">= </span>Grid<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height<span style="font-weight: bold">)
    </span>g<span style="font-weight: bold">.</span>data <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data
    <span style="color: blue; font-weight: bold">return </span>g

  <span style="color: blue; font-weight: bold">def </span>count<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>item <span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True </span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span>sum<span style="font-weight: bold">([</span>x<span style="font-weight: bold">.</span>count<span style="font-weight: bold">(</span>item<span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>data<span style="font-weight: bold">])

  </span><span style="color: blue; font-weight: bold">def </span>asList<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>key <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">):
    </span>list <span style="font-weight: bold">= []
    </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width<span style="font-weight: bold">):
      </span><span style="color: blue; font-weight: bold">for </span>y <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height<span style="font-weight: bold">):
        </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">] == </span>key<span style="font-weight: bold">: </span>list<span style="font-weight: bold">.</span>append<span style="font-weight: bold">( (</span>x<span style="font-weight: bold">,</span>y<span style="font-weight: bold">) )
    </span><span style="color: blue; font-weight: bold">return </span>list

  <span style="color: blue; font-weight: bold">def </span>packBits<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Returns an efficient int list representation

    (width, height, bitPackedInts...)
    """
    </span>bits <span style="font-weight: bold">= [</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height<span style="font-weight: bold">]
    </span>currentInt <span style="font-weight: bold">= </span><span style="color: red">0
    </span><span style="color: blue; font-weight: bold">for </span>i <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height <span style="font-weight: bold">* </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width<span style="font-weight: bold">):
      </span>bit <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>CELLS_PER_INT <span style="font-weight: bold">- (</span>i <span style="font-weight: bold">% </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>CELLS_PER_INT<span style="font-weight: bold">) - </span><span style="color: red">1
      </span>x<span style="font-weight: bold">, </span>y <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_cellIndexToPosition<span style="font-weight: bold">(</span>i<span style="font-weight: bold">)
      </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">]:
        </span>currentInt <span style="font-weight: bold">+= </span><span style="color: red">2 </span><span style="font-weight: bold">** </span>bit
      <span style="color: blue; font-weight: bold">if </span><span style="font-weight: bold">(</span>i <span style="font-weight: bold">+ </span><span style="color: red">1</span><span style="font-weight: bold">) % </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>CELLS_PER_INT <span style="font-weight: bold">== </span><span style="color: red">0</span><span style="font-weight: bold">:
        </span>bits<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span>currentInt<span style="font-weight: bold">)
        </span>currentInt <span style="font-weight: bold">= </span><span style="color: red">0
    </span>bits<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span>currentInt<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">return </span>tuple<span style="font-weight: bold">(</span>bits<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>_cellIndexToPosition<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>index<span style="font-weight: bold">):
    </span>x <span style="font-weight: bold">= </span>index <span style="font-weight: bold">/ </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height
    y <span style="font-weight: bold">= </span>index <span style="font-weight: bold">% </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height
    <span style="color: blue; font-weight: bold">return </span>x<span style="font-weight: bold">, </span>y

  <span style="color: blue; font-weight: bold">def </span>_unpackBits<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>bits<span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Fills in data from a bit-level representation
    """
    </span>cell <span style="font-weight: bold">= </span><span style="color: red">0
    </span><span style="color: blue; font-weight: bold">for </span>packed <span style="color: blue; font-weight: bold">in </span>bits<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">for </span>bit <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_unpackInt<span style="font-weight: bold">(</span>packed<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>CELLS_PER_INT<span style="font-weight: bold">):
        </span><span style="color: blue; font-weight: bold">if </span>cell <span style="font-weight: bold">== </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>width <span style="font-weight: bold">* </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>height<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">break
        </span>x<span style="font-weight: bold">, </span>y <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_cellIndexToPosition<span style="font-weight: bold">(</span>cell<span style="font-weight: bold">)
        </span><span style="color: blue">self</span><span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">] = </span>bit
        cell <span style="font-weight: bold">+= </span><span style="color: red">1

  </span><span style="color: blue; font-weight: bold">def </span>_unpackInt<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>packed<span style="font-weight: bold">, </span>size<span style="font-weight: bold">):
    </span>bools <span style="font-weight: bold">= []
    </span><span style="color: blue; font-weight: bold">if </span>packed <span style="font-weight: bold">&lt; </span><span style="color: red">0</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">raise </span>ValueError<span style="font-weight: bold">, </span><span style="color: red">"must be a positive integer"
    </span><span style="color: blue; font-weight: bold">for </span>i <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>size<span style="font-weight: bold">):
      </span>n <span style="font-weight: bold">= </span><span style="color: red">2 </span><span style="font-weight: bold">** (</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>CELLS_PER_INT <span style="font-weight: bold">- </span>i <span style="font-weight: bold">- </span><span style="color: red">1</span><span style="font-weight: bold">)
      </span><span style="color: blue; font-weight: bold">if </span>packed <span style="font-weight: bold">&gt;= </span>n<span style="font-weight: bold">:
        </span>bools<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">)
        </span>packed <span style="font-weight: bold">-= </span>n
      <span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
        </span>bools<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span><span style="color: blue; font-weight: bold">False</span><span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">return </span>bools

<span style="color: blue; font-weight: bold">def </span>reconstituteGrid<span style="font-weight: bold">(</span>bitRep<span style="font-weight: bold">):
  </span><span style="color: blue; font-weight: bold">if </span>type<span style="font-weight: bold">(</span>bitRep<span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">is not </span>type<span style="font-weight: bold">((</span><span style="color: red">1</span><span style="font-weight: bold">,</span><span style="color: red">2</span><span style="font-weight: bold">)):
    </span><span style="color: blue; font-weight: bold">return </span>bitRep
  width<span style="font-weight: bold">, </span>height <span style="font-weight: bold">= </span>bitRep<span style="font-weight: bold">[:</span><span style="color: red">2</span><span style="font-weight: bold">]
  </span><span style="color: blue; font-weight: bold">return </span>Grid<span style="font-weight: bold">(</span>width<span style="font-weight: bold">, </span>height<span style="font-weight: bold">, </span>bitRepresentation<span style="font-weight: bold">= </span>bitRep<span style="font-weight: bold">[</span><span style="color: red">2</span><span style="font-weight: bold">:])

</span><span style="color: green; font-style: italic">####################################
# Parts you shouldn't have to read #
####################################

</span><span style="color: blue; font-weight: bold">class </span>Actions<span style="font-weight: bold">:
  </span><span style="color: darkred">"""
  A collection of static methods for manipulating move actions.
  """
  </span><span style="color: green; font-style: italic"># Directions
  </span>_directions <span style="font-weight: bold">= {</span>Directions<span style="font-weight: bold">.</span>NORTH<span style="font-weight: bold">: (</span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">1</span><span style="font-weight: bold">),
                 </span>Directions<span style="font-weight: bold">.</span>SOUTH<span style="font-weight: bold">: (</span><span style="color: red">0</span><span style="font-weight: bold">, -</span><span style="color: red">1</span><span style="font-weight: bold">),
                 </span>Directions<span style="font-weight: bold">.</span>EAST<span style="font-weight: bold">:  (</span><span style="color: red">1</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">),
                 </span>Directions<span style="font-weight: bold">.</span>WEST<span style="font-weight: bold">:  (-</span><span style="color: red">1</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">),
                 </span>Directions<span style="font-weight: bold">.</span>STOP<span style="font-weight: bold">:  (</span><span style="color: red">0</span><span style="font-weight: bold">, </span><span style="color: red">0</span><span style="font-weight: bold">)}

  </span>_directionsAsList <span style="font-weight: bold">= </span>_directions<span style="font-weight: bold">.</span>items<span style="font-weight: bold">()

  </span>TOLERANCE <span style="font-weight: bold">= .</span><span style="color: red">001

  </span><span style="color: blue; font-weight: bold">def </span>reverseDirection<span style="font-weight: bold">(</span>action<span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span>action <span style="font-weight: bold">== </span>Directions<span style="font-weight: bold">.</span>NORTH<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span>Directions<span style="font-weight: bold">.</span>SOUTH
    <span style="color: blue; font-weight: bold">if </span>action <span style="font-weight: bold">== </span>Directions<span style="font-weight: bold">.</span>SOUTH<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span>Directions<span style="font-weight: bold">.</span>NORTH
    <span style="color: blue; font-weight: bold">if </span>action <span style="font-weight: bold">== </span>Directions<span style="font-weight: bold">.</span>EAST<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span>Directions<span style="font-weight: bold">.</span>WEST
    <span style="color: blue; font-weight: bold">if </span>action <span style="font-weight: bold">== </span>Directions<span style="font-weight: bold">.</span>WEST<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span>Directions<span style="font-weight: bold">.</span>EAST
    <span style="color: blue; font-weight: bold">return </span>action
  reverseDirection <span style="font-weight: bold">= </span>staticmethod<span style="font-weight: bold">(</span>reverseDirection<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>vectorToDirection<span style="font-weight: bold">(</span>vector<span style="font-weight: bold">):
    </span>dx<span style="font-weight: bold">, </span>dy <span style="font-weight: bold">= </span>vector
    <span style="color: blue; font-weight: bold">if </span>dy <span style="font-weight: bold">&gt; </span><span style="color: red">0</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span>Directions<span style="font-weight: bold">.</span>NORTH
    <span style="color: blue; font-weight: bold">if </span>dy <span style="font-weight: bold">&lt; </span><span style="color: red">0</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span>Directions<span style="font-weight: bold">.</span>SOUTH
    <span style="color: blue; font-weight: bold">if </span>dx <span style="font-weight: bold">&lt; </span><span style="color: red">0</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span>Directions<span style="font-weight: bold">.</span>WEST
    <span style="color: blue; font-weight: bold">if </span>dx <span style="font-weight: bold">&gt; </span><span style="color: red">0</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span>Directions<span style="font-weight: bold">.</span>EAST
    <span style="color: blue; font-weight: bold">return </span>Directions<span style="font-weight: bold">.</span>STOP
  vectorToDirection <span style="font-weight: bold">= </span>staticmethod<span style="font-weight: bold">(</span>vectorToDirection<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>directionToVector<span style="font-weight: bold">(</span>direction<span style="font-weight: bold">, </span>speed <span style="font-weight: bold">= </span><span style="color: red">1.0</span><span style="font-weight: bold">):
    </span>dx<span style="font-weight: bold">, </span>dy <span style="font-weight: bold">=  </span>Actions<span style="font-weight: bold">.</span>_directions<span style="font-weight: bold">[</span>direction<span style="font-weight: bold">]
    </span><span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">(</span>dx <span style="font-weight: bold">* </span>speed<span style="font-weight: bold">, </span>dy <span style="font-weight: bold">* </span>speed<span style="font-weight: bold">)
  </span>directionToVector <span style="font-weight: bold">= </span>staticmethod<span style="font-weight: bold">(</span>directionToVector<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>getPossibleActions<span style="font-weight: bold">(</span>config<span style="font-weight: bold">, </span>walls<span style="font-weight: bold">):
    </span>possible <span style="font-weight: bold">= []
    </span>x<span style="font-weight: bold">, </span>y <span style="font-weight: bold">= </span>config<span style="font-weight: bold">.</span>pos
    x_int<span style="font-weight: bold">, </span>y_int <span style="font-weight: bold">= </span>int<span style="font-weight: bold">(</span>x <span style="font-weight: bold">+ </span><span style="color: red">0.5</span><span style="font-weight: bold">), </span>int<span style="font-weight: bold">(</span>y <span style="font-weight: bold">+ </span><span style="color: red">0.5</span><span style="font-weight: bold">)

    </span><span style="color: green; font-style: italic"># In between grid points, all agents must continue straight
    </span><span style="color: blue; font-weight: bold">if </span><span style="font-weight: bold">(</span>abs<span style="font-weight: bold">(</span>x <span style="font-weight: bold">- </span>x_int<span style="font-weight: bold">) + </span>abs<span style="font-weight: bold">(</span>y <span style="font-weight: bold">- </span>y_int<span style="font-weight: bold">)  &gt; </span>Actions<span style="font-weight: bold">.</span>TOLERANCE<span style="font-weight: bold">):
      </span><span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">[</span>config<span style="font-weight: bold">.</span>getDirection<span style="font-weight: bold">()]

    </span><span style="color: blue; font-weight: bold">for </span>dir<span style="font-weight: bold">, </span>vec <span style="color: blue; font-weight: bold">in </span>Actions<span style="font-weight: bold">.</span>_directionsAsList<span style="font-weight: bold">:
      </span>dx<span style="font-weight: bold">, </span>dy <span style="font-weight: bold">= </span>vec
      next_y <span style="font-weight: bold">= </span>y_int <span style="font-weight: bold">+ </span>dy
      next_x <span style="font-weight: bold">= </span>x_int <span style="font-weight: bold">+ </span>dx
      <span style="color: blue; font-weight: bold">if not </span>walls<span style="font-weight: bold">[</span>next_x<span style="font-weight: bold">][</span>next_y<span style="font-weight: bold">]: </span>possible<span style="font-weight: bold">.</span>append<span style="font-weight: bold">(</span>dir<span style="font-weight: bold">)

    </span><span style="color: blue; font-weight: bold">return </span>possible

  getPossibleActions <span style="font-weight: bold">= </span>staticmethod<span style="font-weight: bold">(</span>getPossibleActions<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>getLegalNeighbors<span style="font-weight: bold">(</span>position<span style="font-weight: bold">, </span>walls<span style="font-weight: bold">):
    </span>x<span style="font-weight: bold">,</span>y <span style="font-weight: bold">= </span>position
    x_int<span style="font-weight: bold">, </span>y_int <span style="font-weight: bold">= </span>int<span style="font-weight: bold">(</span>x <span style="font-weight: bold">+ </span><span style="color: red">0.5</span><span style="font-weight: bold">), </span>int<span style="font-weight: bold">(</span>y <span style="font-weight: bold">+ </span><span style="color: red">0.5</span><span style="font-weight: bold">)
    </span>neighbors <span style="font-weight: bold">= []
    </span><span style="color: blue; font-weight: bold">for </span>dir<span style="font-weight: bold">, </span>vec <span style="color: blue; font-weight: bold">in </span>Actions<span style="font-weight: bold">.</span>_directionsAsList<span style="font-weight: bold">:
      </span>dx<span style="font-weight: bold">, </span>dy <span style="font-weight: bold">= </span>vec
      next_x <span style="font-weight: bold">= </span>x_int <span style="font-weight: bold">+ </span>dx
      <span style="color: blue; font-weight: bold">if </span>next_x <span style="font-weight: bold">&lt; </span><span style="color: red">0 </span><span style="color: blue; font-weight: bold">or </span>next_x <span style="font-weight: bold">== </span>walls<span style="font-weight: bold">.</span>width<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">continue
      </span>next_y <span style="font-weight: bold">= </span>y_int <span style="font-weight: bold">+ </span>dy
      <span style="color: blue; font-weight: bold">if </span>next_y <span style="font-weight: bold">&lt; </span><span style="color: red">0 </span><span style="color: blue; font-weight: bold">or </span>next_y <span style="font-weight: bold">== </span>walls<span style="font-weight: bold">.</span>height<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">continue
      if not </span>walls<span style="font-weight: bold">[</span>next_x<span style="font-weight: bold">][</span>next_y<span style="font-weight: bold">]: </span>neighbors<span style="font-weight: bold">.</span>append<span style="font-weight: bold">((</span>next_x<span style="font-weight: bold">, </span>next_y<span style="font-weight: bold">))
    </span><span style="color: blue; font-weight: bold">return </span>neighbors
  getLegalNeighbors <span style="font-weight: bold">= </span>staticmethod<span style="font-weight: bold">(</span>getLegalNeighbors<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>getSuccessor<span style="font-weight: bold">(</span>position<span style="font-weight: bold">, </span>action<span style="font-weight: bold">):
    </span>dx<span style="font-weight: bold">, </span>dy <span style="font-weight: bold">= </span>Actions<span style="font-weight: bold">.</span>directionToVector<span style="font-weight: bold">(</span>action<span style="font-weight: bold">)
    </span>x<span style="font-weight: bold">, </span>y <span style="font-weight: bold">= </span>position
    <span style="color: blue; font-weight: bold">return </span><span style="font-weight: bold">(</span>x <span style="font-weight: bold">+ </span>dx<span style="font-weight: bold">, </span>y <span style="font-weight: bold">+ </span>dy<span style="font-weight: bold">)
  </span>getSuccessor <span style="font-weight: bold">= </span>staticmethod<span style="font-weight: bold">(</span>getSuccessor<span style="font-weight: bold">)

</span><span style="color: blue; font-weight: bold">class </span>GameStateData<span style="font-weight: bold">:
  </span><span style="color: darkred">"""

  """
  </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>prevState <span style="font-weight: bold">= </span><span style="color: blue">None </span><span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Generates a new data packet by copying information from its predecessor.
    """
    </span><span style="color: blue; font-weight: bold">if </span>prevState <span style="font-weight: bold">!= </span><span style="color: blue">None</span><span style="font-weight: bold">:
      </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>food <span style="font-weight: bold">= </span>prevState<span style="font-weight: bold">.</span>food<span style="font-weight: bold">.</span>shallowCopy<span style="font-weight: bold">()
      </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>capsules <span style="font-weight: bold">= </span>prevState<span style="font-weight: bold">.</span>capsules<span style="font-weight: bold">[:]
      </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentStates <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>copyAgentStates<span style="font-weight: bold">( </span>prevState<span style="font-weight: bold">.</span>agentStates <span style="font-weight: bold">)
      </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>layout <span style="font-weight: bold">= </span>prevState<span style="font-weight: bold">.</span>layout
      <span style="color: blue">self</span><span style="font-weight: bold">.</span>_eaten <span style="font-weight: bold">= </span>prevState<span style="font-weight: bold">.</span>_eaten
      <span style="color: blue">self</span><span style="font-weight: bold">.</span>score <span style="font-weight: bold">= </span>prevState<span style="font-weight: bold">.</span>score
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>_foodEaten <span style="font-weight: bold">= </span><span style="color: blue">None
    self</span><span style="font-weight: bold">.</span>_capsuleEaten <span style="font-weight: bold">= </span><span style="color: blue">None
    self</span><span style="font-weight: bold">.</span>_agentMoved <span style="font-weight: bold">= </span><span style="color: blue">None
    self</span><span style="font-weight: bold">.</span>_lose <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">False
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_win <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">False
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>scoreChange <span style="font-weight: bold">= </span><span style="color: red">0

  </span><span style="color: blue; font-weight: bold">def </span>deepCopy<span style="font-weight: bold">( </span><span style="color: blue">self </span><span style="font-weight: bold">):
    </span>state <span style="font-weight: bold">= </span>GameStateData<span style="font-weight: bold">( </span><span style="color: blue">self </span><span style="font-weight: bold">)
    </span>state<span style="font-weight: bold">.</span>food <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>food<span style="font-weight: bold">.</span>deepCopy<span style="font-weight: bold">()
    </span>state<span style="font-weight: bold">.</span>layout <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>layout<span style="font-weight: bold">.</span>deepCopy<span style="font-weight: bold">()
    </span>state<span style="font-weight: bold">.</span>_agentMoved <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_agentMoved
    state<span style="font-weight: bold">.</span>_foodEaten <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_foodEaten
    state<span style="font-weight: bold">.</span>_capsuleEaten <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_capsuleEaten
    <span style="color: blue; font-weight: bold">return </span>state

  <span style="color: blue; font-weight: bold">def </span>copyAgentStates<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>agentStates <span style="font-weight: bold">):
    </span>copiedStates <span style="font-weight: bold">= []
    </span><span style="color: blue; font-weight: bold">for </span>agentState <span style="color: blue; font-weight: bold">in </span>agentStates<span style="font-weight: bold">:
      </span>copiedStates<span style="font-weight: bold">.</span>append<span style="font-weight: bold">( </span>agentState<span style="font-weight: bold">.</span>copy<span style="font-weight: bold">() )
    </span><span style="color: blue; font-weight: bold">return </span>copiedStates

  <span style="color: blue; font-weight: bold">def </span>__eq__<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>other <span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Allows two states to be compared.
    """
    </span><span style="color: blue; font-weight: bold">if </span>other <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return False
    </span><span style="color: green; font-style: italic"># TODO Check for type of other
    </span><span style="color: blue; font-weight: bold">if not </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentStates <span style="font-weight: bold">== </span>other<span style="font-weight: bold">.</span>agentStates<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return False
    if not </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>food <span style="font-weight: bold">== </span>other<span style="font-weight: bold">.</span>food<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return False
    if not </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>capsules <span style="font-weight: bold">== </span>other<span style="font-weight: bold">.</span>capsules<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return False
    if not </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>score <span style="font-weight: bold">== </span>other<span style="font-weight: bold">.</span>score<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return False
    return True

  def </span>__hash__<span style="font-weight: bold">( </span><span style="color: blue">self </span><span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Allows states to be keys of dictionaries.
    """
    </span><span style="color: blue; font-weight: bold">for </span>i<span style="font-weight: bold">, </span>state <span style="color: blue; font-weight: bold">in </span>enumerate<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentStates <span style="font-weight: bold">):
      </span><span style="color: blue; font-weight: bold">try</span><span style="font-weight: bold">:
        </span>int<span style="font-weight: bold">(</span>hash<span style="font-weight: bold">(</span>state<span style="font-weight: bold">))
      </span><span style="color: blue; font-weight: bold">except </span>TypeError<span style="font-weight: bold">, </span>e<span style="font-weight: bold">:
        </span><span style="color: blue; font-weight: bold">print </span>e
        <span style="color: green; font-style: italic">#hash(state)
    </span><span style="color: blue; font-weight: bold">return </span>int<span style="font-weight: bold">((</span>hash<span style="font-weight: bold">(</span>tuple<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentStates<span style="font-weight: bold">)) + </span><span style="color: red">13</span><span style="font-weight: bold">*</span>hash<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>food<span style="font-weight: bold">) + </span><span style="color: red">113</span><span style="font-weight: bold">* </span>hash<span style="font-weight: bold">(</span>tuple<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>capsules<span style="font-weight: bold">)) + </span><span style="color: red">7 </span><span style="font-weight: bold">* </span>hash<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>score<span style="font-weight: bold">)) % </span><span style="color: red">1048575 </span><span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>__str__<span style="font-weight: bold">( </span><span style="color: blue">self </span><span style="font-weight: bold">):
    </span>width<span style="font-weight: bold">, </span>height <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>layout<span style="font-weight: bold">.</span>width<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>layout<span style="font-weight: bold">.</span>height
    map <span style="font-weight: bold">= </span>Grid<span style="font-weight: bold">(</span>width<span style="font-weight: bold">, </span>height<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">if </span>type<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>food<span style="font-weight: bold">) == </span>type<span style="font-weight: bold">((</span><span style="color: red">1</span><span style="font-weight: bold">,</span><span style="color: red">2</span><span style="font-weight: bold">)):
      </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>food <span style="font-weight: bold">= </span>reconstituteGrid<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>food<span style="font-weight: bold">)
    </span><span style="color: blue; font-weight: bold">for </span>x <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>width<span style="font-weight: bold">):
      </span><span style="color: blue; font-weight: bold">for </span>y <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>height<span style="font-weight: bold">):
        </span>food<span style="font-weight: bold">, </span>walls <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>food<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>layout<span style="font-weight: bold">.</span>walls
        map<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">] = </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_foodWallStr<span style="font-weight: bold">(</span>food<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">], </span>walls<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">])

    </span><span style="color: blue; font-weight: bold">for </span>agentState <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentStates<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">if </span>agentState <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">continue
      if </span>agentState<span style="font-weight: bold">.</span>configuration <span style="font-weight: bold">== </span><span style="color: blue">None</span><span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">continue
      </span>x<span style="font-weight: bold">,</span>y <span style="font-weight: bold">= [</span>int<span style="font-weight: bold">( </span>i <span style="font-weight: bold">) </span><span style="color: blue; font-weight: bold">for </span>i <span style="color: blue; font-weight: bold">in </span>nearestPoint<span style="font-weight: bold">( </span>agentState<span style="font-weight: bold">.</span>configuration<span style="font-weight: bold">.</span>pos <span style="font-weight: bold">)]
      </span>agent_dir <span style="font-weight: bold">= </span>agentState<span style="font-weight: bold">.</span>configuration<span style="font-weight: bold">.</span>direction
      <span style="color: blue; font-weight: bold">if </span>agentState<span style="font-weight: bold">.</span>isPacman<span style="font-weight: bold">:
        </span>map<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">] = </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_pacStr<span style="font-weight: bold">( </span>agent_dir <span style="font-weight: bold">)
      </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
        </span>map<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">] = </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_ghostStr<span style="font-weight: bold">( </span>agent_dir <span style="font-weight: bold">)

    </span><span style="color: blue; font-weight: bold">for </span>x<span style="font-weight: bold">, </span>y <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>capsules<span style="font-weight: bold">:
      </span>map<span style="font-weight: bold">[</span>x<span style="font-weight: bold">][</span>y<span style="font-weight: bold">] = </span><span style="color: red">'o'

    </span><span style="color: blue; font-weight: bold">return </span>str<span style="font-weight: bold">(</span>map<span style="font-weight: bold">) + (</span><span style="color: red">"\nScore: %d\n" </span><span style="font-weight: bold">% </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>score<span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>_foodWallStr<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>hasFood<span style="font-weight: bold">, </span>hasWall <span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span>hasFood<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'.'
    </span><span style="color: blue; font-weight: bold">elif </span>hasWall<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'%'
    </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">' '

  </span><span style="color: blue; font-weight: bold">def </span>_pacStr<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>dir <span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span>dir <span style="font-weight: bold">== </span>Directions<span style="font-weight: bold">.</span>NORTH<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'v'
    </span><span style="color: blue; font-weight: bold">if </span>dir <span style="font-weight: bold">== </span>Directions<span style="font-weight: bold">.</span>SOUTH<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'^'
    </span><span style="color: blue; font-weight: bold">if </span>dir <span style="font-weight: bold">== </span>Directions<span style="font-weight: bold">.</span>WEST<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'&gt;'
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'&lt;'

  </span><span style="color: blue; font-weight: bold">def </span>_ghostStr<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>dir <span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'G'
    </span><span style="color: blue; font-weight: bold">if </span>dir <span style="font-weight: bold">== </span>Directions<span style="font-weight: bold">.</span>NORTH<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'M'
    </span><span style="color: blue; font-weight: bold">if </span>dir <span style="font-weight: bold">== </span>Directions<span style="font-weight: bold">.</span>SOUTH<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'W'
    </span><span style="color: blue; font-weight: bold">if </span>dir <span style="font-weight: bold">== </span>Directions<span style="font-weight: bold">.</span>WEST<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'3'
    </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">'E'

  </span><span style="color: blue; font-weight: bold">def </span>initialize<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>layout<span style="font-weight: bold">, </span>numGhostAgents <span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Creates an initial game state from a layout array (see layout.py).
    """
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>food <span style="font-weight: bold">= </span>layout<span style="font-weight: bold">.</span>food<span style="font-weight: bold">.</span>copy<span style="font-weight: bold">()
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>capsules <span style="font-weight: bold">= </span>layout<span style="font-weight: bold">.</span>capsules<span style="font-weight: bold">[:]
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>layout <span style="font-weight: bold">= </span>layout
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>score <span style="font-weight: bold">= </span><span style="color: red">0
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>scoreChange <span style="font-weight: bold">= </span><span style="color: red">0

    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentStates <span style="font-weight: bold">= []
    </span>numGhosts <span style="font-weight: bold">= </span><span style="color: red">0
    </span><span style="color: blue; font-weight: bold">for </span>isPacman<span style="font-weight: bold">, </span>pos <span style="color: blue; font-weight: bold">in </span>layout<span style="font-weight: bold">.</span>agentPositions<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">if not </span>isPacman<span style="font-weight: bold">:
        </span><span style="color: blue; font-weight: bold">if </span>numGhosts <span style="font-weight: bold">== </span>numGhostAgents<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">continue </span><span style="color: green; font-style: italic"># Max ghosts reached already
        </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">: </span>numGhosts <span style="font-weight: bold">+= </span><span style="color: red">1
      </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentStates<span style="font-weight: bold">.</span>append<span style="font-weight: bold">( </span>AgentState<span style="font-weight: bold">( </span>Configuration<span style="font-weight: bold">( </span>pos<span style="font-weight: bold">, </span>Directions<span style="font-weight: bold">.</span>STOP<span style="font-weight: bold">), </span>isPacman<span style="font-weight: bold">) )
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_eaten <span style="font-weight: bold">= [</span><span style="color: blue; font-weight: bold">False for </span>a <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentStates<span style="font-weight: bold">]

</span><span style="color: blue; font-weight: bold">class </span>Game<span style="font-weight: bold">:
  </span><span style="color: darkred">"""
  The Game manages the control flow, soliciting actions from agents.
  """

  </span><span style="color: blue; font-weight: bold">def </span>__init__<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>agents<span style="font-weight: bold">, </span>display<span style="font-weight: bold">, </span>rules<span style="font-weight: bold">, </span>startingIndex<span style="font-weight: bold">=</span><span style="color: red">0</span><span style="font-weight: bold">, </span>muteAgents<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">False</span><span style="font-weight: bold">, </span>catchExceptions<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">False </span><span style="font-weight: bold">):
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentCrashed <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">False
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agents <span style="font-weight: bold">= </span>agents
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>display <span style="font-weight: bold">= </span>display
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>rules <span style="font-weight: bold">= </span>rules
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>startingIndex <span style="font-weight: bold">= </span>startingIndex
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>gameOver <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">False
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>muteAgents <span style="font-weight: bold">= </span>muteAgents
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>catchExceptions <span style="font-weight: bold">= </span>catchExceptions
    <span style="color: blue">self</span><span style="font-weight: bold">.</span>moveHistory <span style="font-weight: bold">= []
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>totalAgentTimes <span style="font-weight: bold">= [</span><span style="color: red">0 </span><span style="color: blue; font-weight: bold">for </span>agent <span style="color: blue; font-weight: bold">in </span>agents<span style="font-weight: bold">]
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>totalAgentTimeWarnings <span style="font-weight: bold">= [</span><span style="color: red">0 </span><span style="color: blue; font-weight: bold">for </span>agent <span style="color: blue; font-weight: bold">in </span>agents<span style="font-weight: bold">]
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentTimeout <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">False

  def </span>getProgress<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>gameOver<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: red">1.0
    </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">return </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>rules<span style="font-weight: bold">.</span>getProgress<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">)

  </span><span style="color: blue; font-weight: bold">def </span>_agentCrash<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">, </span>agentIndex<span style="font-weight: bold">, </span>quiet<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">False</span><span style="font-weight: bold">):
    </span><span style="color: red">"Helper method for handling agent crashes"
    </span><span style="color: blue; font-weight: bold">if not </span>quiet<span style="font-weight: bold">: </span>traceback<span style="font-weight: bold">.</span>print_exc<span style="font-weight: bold">()
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>gameOver <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">True
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentCrashed <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">True
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>rules<span style="font-weight: bold">.</span>agentCrash<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">, </span>agentIndex<span style="font-weight: bold">)

  </span>OLD_STDOUT <span style="font-weight: bold">= </span><span style="color: blue">None
  </span>OLD_STDERR <span style="font-weight: bold">= </span><span style="color: blue">None

  </span><span style="color: blue; font-weight: bold">def </span>mute<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if not </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>muteAgents<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return
    global </span>OLD_STDOUT<span style="font-weight: bold">, </span>OLD_STDERR
    <span style="color: blue; font-weight: bold">import </span>cStringIO
    OLD_STDOUT <span style="font-weight: bold">= </span>sys<span style="font-weight: bold">.</span>stdout
    OLD_STDERR <span style="font-weight: bold">= </span>sys<span style="font-weight: bold">.</span>stderr
    sys<span style="font-weight: bold">.</span>stdout <span style="font-weight: bold">= </span>cStringIO<span style="font-weight: bold">.</span>StringIO<span style="font-weight: bold">()
    </span>sys<span style="font-weight: bold">.</span>stderr <span style="font-weight: bold">= </span>cStringIO<span style="font-weight: bold">.</span>StringIO<span style="font-weight: bold">()

  </span><span style="color: blue; font-weight: bold">def </span>unmute<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">):
    </span><span style="color: blue; font-weight: bold">if not </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>muteAgents<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">return
    global </span>OLD_STDOUT<span style="font-weight: bold">, </span>OLD_STDERR
    sys<span style="font-weight: bold">.</span>stdout<span style="font-weight: bold">.</span>close<span style="font-weight: bold">()
    </span>sys<span style="font-weight: bold">.</span>stderr<span style="font-weight: bold">.</span>close<span style="font-weight: bold">()
    </span><span style="color: green; font-style: italic"># Revert stdout/stderr to originals
    </span>sys<span style="font-weight: bold">.</span>stdout <span style="font-weight: bold">= </span>OLD_STDOUT
    sys<span style="font-weight: bold">.</span>stderr <span style="font-weight: bold">= </span>OLD_STDERR


  <span style="color: blue; font-weight: bold">def </span>run<span style="font-weight: bold">( </span><span style="color: blue">self </span><span style="font-weight: bold">):
    </span><span style="color: darkred">"""
    Main control loop for game play.
    """
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>display<span style="font-weight: bold">.</span>initialize<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state<span style="font-weight: bold">.</span>data<span style="font-weight: bold">)
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>numMoves <span style="font-weight: bold">= </span><span style="color: red">0

    </span><span style="color: green; font-style: italic">###self.display.initialize(self.state.makeObservation(1).data)
    # inform learning agents of the game start
    </span><span style="color: blue; font-weight: bold">for </span>i <span style="color: blue; font-weight: bold">in </span>range<span style="font-weight: bold">(</span>len<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agents<span style="font-weight: bold">)):
      </span>agent <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agents<span style="font-weight: bold">[</span>i<span style="font-weight: bold">]
      </span><span style="color: blue; font-weight: bold">if not </span>agent<span style="font-weight: bold">:
        </span><span style="color: green; font-style: italic"># this is a null agent, meaning it failed to load
        # the other team wins
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_agentCrash<span style="font-weight: bold">(</span>i<span style="font-weight: bold">, </span>quiet<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">)
        </span><span style="color: blue; font-weight: bold">return
      if </span><span style="font-weight: bold">(</span><span style="color: red">"registerInitialState" </span><span style="color: blue; font-weight: bold">in </span>dir<span style="font-weight: bold">(</span>agent<span style="font-weight: bold">)):
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>mute<span style="font-weight: bold">()
        </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>catchExceptions<span style="font-weight: bold">:
          </span><span style="color: blue; font-weight: bold">try</span><span style="font-weight: bold">:
            </span>timed_func <span style="font-weight: bold">= </span>TimeoutFunction<span style="font-weight: bold">(</span>agent<span style="font-weight: bold">.</span>registerInitialState<span style="font-weight: bold">, </span>int<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>rules<span style="font-weight: bold">.</span>getMaxStartupTime<span style="font-weight: bold">(</span>i<span style="font-weight: bold">)))
            </span><span style="color: blue; font-weight: bold">try</span><span style="font-weight: bold">:
              </span>start_time <span style="font-weight: bold">= </span>time<span style="font-weight: bold">.</span>time<span style="font-weight: bold">()
              </span>timed_func<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state<span style="font-weight: bold">.</span>deepCopy<span style="font-weight: bold">())
              </span>time_taken <span style="font-weight: bold">= </span>time<span style="font-weight: bold">.</span>time<span style="font-weight: bold">() - </span>start_time
              <span style="color: blue">self</span><span style="font-weight: bold">.</span>totalAgentTimes<span style="font-weight: bold">[</span>i<span style="font-weight: bold">] += </span>time_taken
            <span style="color: blue; font-weight: bold">except </span>TimeoutFunctionException<span style="font-weight: bold">:
              </span><span style="color: blue; font-weight: bold">print </span><span style="color: red">"Agent %d ran out of time on startup!" </span><span style="font-weight: bold">% </span>i
              <span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
              </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentTimeout <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">True
              </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_agentCrash<span style="font-weight: bold">(</span>i<span style="font-weight: bold">, </span>quiet<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">)
              </span><span style="color: blue; font-weight: bold">return
          except </span>Exception<span style="font-weight: bold">,</span>data<span style="font-weight: bold">:
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_agentCrash<span style="font-weight: bold">(</span>i<span style="font-weight: bold">, </span>quiet<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">)
            </span><span style="color: blue; font-weight: bold">return
        else</span><span style="font-weight: bold">:
          </span>agent<span style="font-weight: bold">.</span>registerInitialState<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state<span style="font-weight: bold">.</span>deepCopy<span style="font-weight: bold">())
        </span><span style="color: green; font-style: italic">## TODO: could this exceed the total time
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()

    </span>agentIndex <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>startingIndex
    numAgents <span style="font-weight: bold">= </span>len<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agents <span style="font-weight: bold">)

    </span><span style="color: blue; font-weight: bold">while not </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>gameOver<span style="font-weight: bold">:
      </span><span style="color: green; font-style: italic"># Fetch the next agent
      </span>agent <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agents<span style="font-weight: bold">[</span>agentIndex<span style="font-weight: bold">]
      </span>move_time <span style="font-weight: bold">= </span><span style="color: red">0
      </span>skip_action <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">False
      </span><span style="color: green; font-style: italic"># Generate an observation of the state
      </span><span style="color: blue; font-weight: bold">if </span><span style="color: red">'observationFunction' </span><span style="color: blue; font-weight: bold">in </span>dir<span style="font-weight: bold">( </span>agent <span style="font-weight: bold">):
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>mute<span style="font-weight: bold">()
        </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>catchExceptions<span style="font-weight: bold">:
          </span><span style="color: blue; font-weight: bold">try</span><span style="font-weight: bold">:
            </span>timed_func <span style="font-weight: bold">= </span>TimeoutFunction<span style="font-weight: bold">(</span>agent<span style="font-weight: bold">.</span>observationFunction<span style="font-weight: bold">, </span>int<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>rules<span style="font-weight: bold">.</span>getMoveTimeout<span style="font-weight: bold">(</span>agentIndex<span style="font-weight: bold">)))
            </span><span style="color: blue; font-weight: bold">try</span><span style="font-weight: bold">:
              </span>start_time <span style="font-weight: bold">= </span>time<span style="font-weight: bold">.</span>time<span style="font-weight: bold">()
              </span>observation <span style="font-weight: bold">= </span>timed_func<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state<span style="font-weight: bold">.</span>deepCopy<span style="font-weight: bold">())
            </span><span style="color: blue; font-weight: bold">except </span>TimeoutFunctionException<span style="font-weight: bold">:
              </span>skip_action <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">True
            </span>move_time <span style="font-weight: bold">+= </span>time<span style="font-weight: bold">.</span>time<span style="font-weight: bold">() - </span>start_time
            <span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
          </span><span style="color: blue; font-weight: bold">except </span>Exception<span style="font-weight: bold">,</span>data<span style="font-weight: bold">:
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_agentCrash<span style="font-weight: bold">(</span>agentIndex<span style="font-weight: bold">, </span>quiet<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">)
            </span><span style="color: blue; font-weight: bold">return
        else</span><span style="font-weight: bold">:
          </span>observation <span style="font-weight: bold">= </span>agent<span style="font-weight: bold">.</span>observationFunction<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state<span style="font-weight: bold">.</span>deepCopy<span style="font-weight: bold">())
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
      </span><span style="color: blue; font-weight: bold">else</span><span style="font-weight: bold">:
        </span>observation <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state<span style="font-weight: bold">.</span>deepCopy<span style="font-weight: bold">()

      </span><span style="color: green; font-style: italic"># Solicit an action
      </span>action <span style="font-weight: bold">= </span><span style="color: blue">None
      self</span><span style="font-weight: bold">.</span>mute<span style="font-weight: bold">()
      </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>catchExceptions<span style="font-weight: bold">:
        </span><span style="color: blue; font-weight: bold">try</span><span style="font-weight: bold">:
          </span>timed_func <span style="font-weight: bold">= </span>TimeoutFunction<span style="font-weight: bold">(</span>agent<span style="font-weight: bold">.</span>getAction<span style="font-weight: bold">, </span>int<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>rules<span style="font-weight: bold">.</span>getMoveTimeout<span style="font-weight: bold">(</span>agentIndex<span style="font-weight: bold">)) - </span>int<span style="font-weight: bold">(</span>move_time<span style="font-weight: bold">))
          </span><span style="color: blue; font-weight: bold">try</span><span style="font-weight: bold">:
            </span>start_time <span style="font-weight: bold">= </span>time<span style="font-weight: bold">.</span>time<span style="font-weight: bold">()
            </span><span style="color: blue; font-weight: bold">if </span>skip_action<span style="font-weight: bold">:
              </span><span style="color: blue; font-weight: bold">raise </span>TimeoutFunctionException<span style="font-weight: bold">()
            </span>action <span style="font-weight: bold">= </span>timed_func<span style="font-weight: bold">( </span>observation <span style="font-weight: bold">)
          </span><span style="color: blue; font-weight: bold">except </span>TimeoutFunctionException<span style="font-weight: bold">:
            </span><span style="color: blue; font-weight: bold">print </span><span style="color: red">"Agent %d timed out on a single move!" </span><span style="font-weight: bold">% </span>agentIndex
            <span style="color: blue">self</span><span style="font-weight: bold">.</span>agentTimeout <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">True
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_agentCrash<span style="font-weight: bold">(</span>agentIndex<span style="font-weight: bold">, </span>quiet<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">)
            </span><span style="color: blue; font-weight: bold">return

          </span>move_time <span style="font-weight: bold">+= </span>time<span style="font-weight: bold">.</span>time<span style="font-weight: bold">() - </span>start_time

          <span style="color: blue; font-weight: bold">if </span>move_time <span style="font-weight: bold">&gt; </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>rules<span style="font-weight: bold">.</span>getMoveWarningTime<span style="font-weight: bold">(</span>agentIndex<span style="font-weight: bold">):
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>totalAgentTimeWarnings<span style="font-weight: bold">[</span>agentIndex<span style="font-weight: bold">] += </span><span style="color: red">1
            </span><span style="color: blue; font-weight: bold">print </span><span style="color: red">"Agent %d took too long to make a move! This is warning %d" </span><span style="font-weight: bold">% (</span>agentIndex<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>totalAgentTimeWarnings<span style="font-weight: bold">[</span>agentIndex<span style="font-weight: bold">])
            </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>totalAgentTimeWarnings<span style="font-weight: bold">[</span>agentIndex<span style="font-weight: bold">] &gt; </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>rules<span style="font-weight: bold">.</span>getMaxTimeWarnings<span style="font-weight: bold">(</span>agentIndex<span style="font-weight: bold">):
              </span><span style="color: blue; font-weight: bold">print </span><span style="color: red">"Agent %d exceeded the maximum number of warnings: %d" </span><span style="font-weight: bold">% (</span>agentIndex<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>totalAgentTimeWarnings<span style="font-weight: bold">[</span>agentIndex<span style="font-weight: bold">])
              </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentTimeout <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">True
              </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
              </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_agentCrash<span style="font-weight: bold">(</span>agentIndex<span style="font-weight: bold">, </span>quiet<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">)

          </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>totalAgentTimes<span style="font-weight: bold">[</span>agentIndex<span style="font-weight: bold">] += </span>move_time
          <span style="color: green; font-style: italic">#print "Agent: %d, time: %f, total: %f" % (agentIndex, move_time, self.totalAgentTimes[agentIndex])
          </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>totalAgentTimes<span style="font-weight: bold">[</span>agentIndex<span style="font-weight: bold">] &gt; </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>rules<span style="font-weight: bold">.</span>getMaxTotalTime<span style="font-weight: bold">(</span>agentIndex<span style="font-weight: bold">):
            </span><span style="color: blue; font-weight: bold">print </span><span style="color: red">"Agent %d ran out of time! (time: %1.2f)" </span><span style="font-weight: bold">% (</span>agentIndex<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>totalAgentTimes<span style="font-weight: bold">[</span>agentIndex<span style="font-weight: bold">])
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agentTimeout <span style="font-weight: bold">= </span><span style="color: blue; font-weight: bold">True
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
            </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_agentCrash<span style="font-weight: bold">(</span>agentIndex<span style="font-weight: bold">, </span>quiet<span style="font-weight: bold">=</span><span style="color: blue; font-weight: bold">True</span><span style="font-weight: bold">)
            </span><span style="color: blue; font-weight: bold">return
          </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
        </span><span style="color: blue; font-weight: bold">except </span>Exception<span style="font-weight: bold">,</span>data<span style="font-weight: bold">:
          </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
          </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_agentCrash<span style="font-weight: bold">(</span>agentIndex<span style="font-weight: bold">)
          </span><span style="color: blue; font-weight: bold">return
      else</span><span style="font-weight: bold">:
        </span>action <span style="font-weight: bold">= </span>agent<span style="font-weight: bold">.</span>getAction<span style="font-weight: bold">(</span>observation<span style="font-weight: bold">)
      </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()

      </span><span style="color: green; font-style: italic"># Execute the action
      </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>moveHistory<span style="font-weight: bold">.</span>append<span style="font-weight: bold">( (</span>agentIndex<span style="font-weight: bold">, </span>action<span style="font-weight: bold">) )
      </span><span style="color: blue; font-weight: bold">if </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>catchExceptions<span style="font-weight: bold">:
        </span><span style="color: blue; font-weight: bold">try</span><span style="font-weight: bold">:
          </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state<span style="font-weight: bold">.</span>generateSuccessor<span style="font-weight: bold">( </span>agentIndex<span style="font-weight: bold">, </span>action <span style="font-weight: bold">)
        </span><span style="color: blue; font-weight: bold">except </span>Exception<span style="font-weight: bold">,</span>data<span style="font-weight: bold">:
          </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>_agentCrash<span style="font-weight: bold">(</span>agentIndex<span style="font-weight: bold">)
          </span><span style="color: blue; font-weight: bold">return
      else</span><span style="font-weight: bold">:
        </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state <span style="font-weight: bold">= </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state<span style="font-weight: bold">.</span>generateSuccessor<span style="font-weight: bold">( </span>agentIndex<span style="font-weight: bold">, </span>action <span style="font-weight: bold">)

      </span><span style="color: green; font-style: italic"># Change the display
      </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>display<span style="font-weight: bold">.</span>update<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state<span style="font-weight: bold">.</span>data <span style="font-weight: bold">)
      </span><span style="color: green; font-style: italic">###idx = agentIndex - agentIndex % 2 + 1
      ###self.display.update( self.state.makeObservation(idx).data )

      # Allow for game specific conditions (winning, losing, etc.)
      </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>rules<span style="font-weight: bold">.</span>process<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state<span style="font-weight: bold">, </span><span style="color: blue">self</span><span style="font-weight: bold">)
      </span><span style="color: green; font-style: italic"># Track progress
      </span><span style="color: blue; font-weight: bold">if </span>agentIndex <span style="font-weight: bold">== </span>numAgents <span style="font-weight: bold">+ </span><span style="color: red">1</span><span style="font-weight: bold">: </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>numMoves <span style="font-weight: bold">+= </span><span style="color: red">1
      </span><span style="color: green; font-style: italic"># Next agent
      </span>agentIndex <span style="font-weight: bold">= ( </span>agentIndex <span style="font-weight: bold">+ </span><span style="color: red">1 </span><span style="font-weight: bold">) % </span>numAgents

      <span style="color: blue; font-weight: bold">if </span>_BOINC_ENABLED<span style="font-weight: bold">:
        </span>boinc<span style="font-weight: bold">.</span>set_fraction_done<span style="font-weight: bold">(</span><span style="color: blue">self</span><span style="font-weight: bold">.</span>getProgress<span style="font-weight: bold">())

    </span><span style="color: green; font-style: italic"># inform a learning agent of the game result
    </span><span style="color: blue; font-weight: bold">for </span>agent <span style="color: blue; font-weight: bold">in </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>agents<span style="font-weight: bold">:
      </span><span style="color: blue; font-weight: bold">if </span><span style="color: red">"final" </span><span style="color: blue; font-weight: bold">in </span>dir<span style="font-weight: bold">( </span>agent <span style="font-weight: bold">) :
        </span><span style="color: blue; font-weight: bold">try</span><span style="font-weight: bold">:
          </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>mute<span style="font-weight: bold">()
          </span>agent<span style="font-weight: bold">.</span>final<span style="font-weight: bold">( </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>state <span style="font-weight: bold">)
          </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
        </span><span style="color: blue; font-weight: bold">except </span>Exception<span style="font-weight: bold">,</span>data<span style="font-weight: bold">:
          </span><span style="color: blue; font-weight: bold">if not </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>catchExceptions<span style="font-weight: bold">: </span><span style="color: blue; font-weight: bold">raise
          </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>unmute<span style="font-weight: bold">()
          </span><span style="color: blue; font-weight: bold">print </span><span style="color: red">"Exception"</span><span style="font-weight: bold">,</span>data
          <span style="color: blue">self</span><span style="font-weight: bold">.</span>_agentCrash<span style="font-weight: bold">(</span>agent<span style="font-weight: bold">.</span>index<span style="font-weight: bold">)
          </span><span style="color: blue; font-weight: bold">return
    </span><span style="color: blue">self</span><span style="font-weight: bold">.</span>display<span style="font-weight: bold">.</span>finish<span style="font-weight: bold">()




</span>
  </pre>
  </body>
  </html>
  